As is well-known in the art, general-purpose microprocessors and microcontrollers are used in system control, and to apply the intelligence of such processors to real systems is often achieved with software under the control of some sort of an operating system (OS). An OS is a high-level computer program implemented as either software or firmware in operating a microcontroller or microprocessor in conjunction with system sensors (input) and operators (output), and coded subroutines in performing systems tasks. The OS provides a framework and imposes operating rules and constraints in integrating subroutines in accomplishing specific system tasks. Programmers have at their disposal a variety of programming models to choose from when creating hardware/software control systems, which comprise programs (software) which run on the microprocessors and microcontrollers (hardware).
For reference in understanding the present invention the inventor incorporates herein by reference the following book:
Many of the terms and concepts used in this application may be better understood with reference to this book.
Two significant models that dictate overall behavior of a comprehensive program are the foreground-background loop and kernel-based multitasking. Each of these models is explained in some detail in the attached Appendix. In both models, the flow of program execution is governed by actions and events. A program which employs a foreground-background loop performs actions repetitively, sequentially and indefinitely (hence the loop). For example, for three actions A, B and C, the sequence of execution for a foreground/background-type program is as shown in the time diagram of FIG. 1. The sequence is from left to right in advancing time, and it is seen that actions A, B, and C repeat in sequence endlessly.
Because this sequence is fixed sequentially, because each action must run until completion, and because the time between successive same actions can be of long duration, the actions in the loop are not well-suited to providing rapid responses to external events. Instead, interrupts are often used to perform time-critical actions in response to external (e.g. keypresses) or internal (e.g. repetitive timer) events. An interrupt I might occur in the loop illustrated as FIG. 1, as shown in FIG. 2. It is seen that the normal sequence of operations may be interrupted any number of times, and, when the interrupt is finished, the sequence resumes where it left off. The interrupts, indicated as I in every case, although there may be more than one kind of interrupt, may occur of course at any point in the loop progression.
Because the loop system's response to an interrupt-driven event is much faster than the time between successive same actions, A-to-A for example, the interrupts are said to occur in the foreground, and the actions in the loop occur in the background. Interrupts can be of several sorts, as mentioned above, and are often used as a mechanism to pass information (e.g. an event has occurred) from the foreground to the background, where the event may be acted upon. The use of global variables and the selective control of interrupts are two of several methods employed to communicate between the foreground and the background in looped systems.
An important advantage of a foreground-background architecture is that such an architecture is relatively simple when a small number of actions are involved. However, as the complexity of a system rises, it is generally accepted in the art that a foreground-background system becomes increasingly difficult to understand, to properly characterize, and to expand and maintain. The inflexibility of the task execution sequence results in response time(s) suffering as well. Foreground-background loop systems can be extended via the use of state machines in order to control the sequencing of actions, but ultimately such an architecture affords the programmer inadequate flexibility in maximizing the system's performance and tailoring its responsiveness.
To counter the problem of unresponsive foreground/background-type systems, the notion of kernel-based multitasking was developed. Among the goals of kernel-based multitasking is to make efficient use of the processor's power, to maximize the system's event-response time, to manage complexity, and to provide for reliable communications between different parts of the overall program.
In kernel-based multitasking, actions in the form of independent subprograms are referred to as tasks (or threads or processes, etc.), and a notion of task priorities is introduced. The kernel is a small sub-program which ensures that the highest-priority task is always the one about to run or actually. Task switching, occurs when the running task relinquishes (in a cooperative system) or is forced to relinquish (in a preemptive system) control of the processor's resources (e.g. program counter and possibly other, typically memory, resources) to another task, which then takes control and begins executing. (This is a process which will be quite familiar to those with skill in the art of higher-power microprocessors). Task switches are managed by the kernel. A context switch generally suspends or stops one task and resumes or starts another, and additionally saves the context of the suspended task so that the task, when resumed, may continue where it was suspended with its entire context (e.g. all of the processor's internal registers) unchanged from when it was suspended.
For example, for three tasks A, B and C with decreasing priorities, the sequence of execution for a kernel-driven, multitasking system might be as shown in FIG. 3. Notice that in the sequence shown in FIG. 3 some instances of task execution complete before another task starts. For example, task B initially runs to completion because its priority exceeds that of task C, and the multitasking kernel has not yet made task A eligible to run. However, the next time task B runs it is suspended while the higher-priority task A runs to completion, whereupon task B resumes running.
This task execution by priority is one of the hallmarks of kernel-based multitasking. Interrupts may also be interspersed within the above sequence. Finally, events are used as a means of communicating among tasks or between tasks and internal and external stimuli.
Another type of multitasking is time-sliced multitasking. Time-sliced multitasking controls task execution based on an additional parameter, namely the amount of time each task is allowed to run. This type of multitasking is also managed by a kernel.
A kernel's behavior can often be characterized precisely enough to specify in a fully deterministic manner how long any operation (e.g. a context switch) will take. Such a kernel is said to provide real-time multitasking. The combination of such a kernel and all the accompanying task and event functionality is known in the art as a real-time operating system (RTOS). The present invention is an RTOS.
RTOS tasks exist independently of one another. Global variables and interrupt control are used for simple intercommunication. More sophisticated intercommunication is accomplished in such a system via events such as semaphores, messages and message queues, whose behavior is controlled by the RTOS. When and how long a task runs is governed by its priority, the system's other tasks, the occurrence of events and other factors (e.g. the control of interrupts). Context switches occur for a variety of reasons, including the need for a higher priority task to run, the desire to delay a task for a specified time interval, or an attempt to communicate with a task when the desired information is not (yet) available. A context switch changes the running state of the current task to be either eligible, delayed, waiting, stopped, etc. In a preemptive system, a context switch may occur at any random time and at any subroutine call depth in the task. The depth at which context switches may occur is important in the present invention.
A cooperative system is similar to the pre-emptive system described above, but a context switch may only occur when and where the programmer has requested or allowed a context switch to occur. Since, when a subroutine or task is pre-empted in either type system, its return addresses are normally kept on a stack, the kernel must maintain a separate stack for each task so that when a task resumes, its subroutines are able to return back up the call tree. Context-sensitive information (e.g. the task's resume address and register values) is often also saved on the task stack.
As an example, a task T1 may call subroutines S1—1 and S1—2. Subroutine S1—1 may itself call subroutines S1—1—1 and S1—1—2, and subroutine S1—1—2 may call a subroutine S1—1—2—1. Task T1's call tree will look like:
                            ⁢                  T          ⁢                                          ⁢          1                                                  +                      --                          --                              -                                  --                  S1_                                                                    ⁢        1                                ❘                              +                          --                              --                                  --                                      --                    S1_                                                                                ⁢          1          ⁢          _          ⁢          1                                        ❘                              +                          --                              --                                  --                                      --                    S1_                                                                                ⁢          1          ⁢          _          ⁢          2                                        ❘                              +                          --                              --                                  --                                      --                    S1_                                                                                ⁢          1          ⁢          _          ⁢          2          ⁢          _          ⁢          1                                                ⁢                              +                          --                              --                                  -                                      --                    S1_                                                                                ⁢          2                    
When a context switch occurs in subroutine S1—1—2—1 while task T1 is running, task T1's call . . . return stack will contain
top of stack -> return address in S1_1_2return address in S1_1return address in T1
This call . . . return stack is unique to task T1. When task T1 resumes after this context switch, each subroutine must successfully return to the position from where it was called in order for task T1 to continue executing properly. The kernel is responsible for managing all the stacks in the RTOS.
Architecture dictates the capabilities of a processor's stack. In a general-purpose stack (e.g. Motorola 68000 series microprocessors), the size of the stack is limited only by available RAM. Because the stack's contents are not constrained, a general-purpose stack can include subroutine return addresses. An RTOS allocates task stack memory based partially on the amount of memory required to store return addresses for the expected maximum call depth. As maximum call depth and/or the number of tasks in a system grows, so do its RAM requirements. RAM requirements per task for a typical RTOS range from hundreds of bytes to kilobytes or in some cases even megabytes per task. An RTOS may also allocate additional memory on a per-task basis fur task-specific information, e.g. its priority and context-saving information.
Given the above descriptions, as current RTOS design presupposes the existence of one or more general-purpose stacks or similar memory blocks for the saving of return addresses, the RAM requirements of such an RTOS are a direct consequence of the RTOS' support for context switching at any call depth.
The typically very large RAM requirement for an RTOS supporting context switching at any call depth effectively preclude the use of an RTOS in a class of processors (usually microcontrollers) which have very little RAM, from tens to hundreds to perhaps as much as a few kilobytes of RAM. Such processors may have a general-purpose stack, or they may have a single hardware call . . . return stack, which provides for a restricted subroutine call depth (often limited to 2-16 levels), with only return addresses stored on the stack. In either case there is too little memory to devote to individual task stacks.
Thus the memory-hungry nature of a conventional RTOS precludes use of such an operating systems with memory-challenged microcontrollers. What is therefore clearly needed is an RTOS that may be used with such controllers, which would significantly increase the range of uses for such controllers, and allow system design for sophisticated systems using less expensive controllers than would otherwise be the case.